#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/6 16:24
# @USER    : Shengji He
# @File    : PalindromePairs.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        """
        Given a list of unique words, find all pairs of distinct indices (i, j) in the given list,
        so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

        Example 1:
            Input: ["abcd","dcba","lls","s","sssll"]

            Output: [[0,1],[1,0],[3,2],[2,4]]

            Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
        Example 2:
            Input: ["bat","tab","cat"]

            Output: [[0,1],[1,0]]

            Explanation: The palindromes are ["battab","tabbat"]

        :param words:
        :return:
        """
        words_dict = {w: i for i, w in enumerate(words)}
        ans = []
        for i, w in enumerate(words):
            pre, suf = self.palindromeFix(w)
            for p in pre:
                if p in words_dict and i != words_dict[p] and p[::-1] != w:
                    ans.append([words_dict[p], i])
            for s in suf:
                if s in words_dict and i != words_dict[s]:
                    ans.append([i, words_dict[s]])

        return ans

    @staticmethod
    def palindromeFix(word: str):
        pre, suf = [], []
        for i in range(len(word) + 1):
            if word[:i] == word[:i][::-1]:
                pre.append(word[i:][::-1])

            if word[i:] == word[i:][::-1]:
                suf.append(word[:i][::-1])
        return pre, suf


if __name__ == '__main__':
    S = Solution()
    words = ["bat", "tab", "cat"]
    # words = ["abcd", "dcba", "lls", "s", "sssll"]
    print(S.palindromePairs(words))
    print('done')
